package com.jeff.interview;

/**
 * linyu l00805065
 * 一只青蛙想要过河。假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子(也有可能没有)。青蛙可以跳上石子，但是不可以跳入水中。
 * 给你石子的位置列表 stones (用单元格序号升序 表示)， 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。
 * 开始时，青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位(即只能从单元格 1 跳至单元格 2)。
 * 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方(终点的方向)跳跃。
 * <p>
 * 示例 1：
 * 输入：stones = [0,1,3,5,6,8,12,17]
 * river = [1,1,0,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1]
 * 输出：true
 * 解释：青蛙可以成功过河，按照如下方案跳跃，
 * 跳 1 个单位到第 2 块石子，
 * 然后跳 2 个单位到第 3 块石子，
 * 接着 跳 2 个单位到第 4 块石子，
 * 然后跳 3 个单位到第 6 块石子，
 * 跳 4 个单位到第 7 块石子，
 * 最后，跳 5 个单位到第 8 个石子(即最后一块石子)。
 * <p>
 * 示例 2：
 * 输入：stones = [0,1,2,3,4,8,9,11]
 * 输出：false
 * 解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
 */
//自己基于规则来解决 面向过程编程
public class Test3 {
    public static void main(String[] args) {
        int[] stones1 = {0, 1, 3, 5, 6, 8, 12, 17};
        int[] stones2 = {0, 1, 2, 3, 4, 8, 9, 11};
        System.out.println(jump(stones1));
        System.out.println(jump(stones2));
    }

    public static boolean jump(int[] stones) {
        //声明一个河流数组
        int[] river = new int[stones[stones.length - 1] + 1];
        river[0] = 1;
        //第一步只能跳一下 所以第二个格子必须得有石头才可以
        if (stones[1] == 0) {
            return false;
        }
        river[1] = 1;
        //根据输入的石头数组,初始化河流数组
        for (int i = 2; i < stones.length; i++) {
            int riverIndex = stones[i];
            river[riverIndex] = 1;
        }
        //遍历整个石头数组 判断最后一步是否能跳到最后一个石子上 如果能跳到终点就返回1,否则返回0
        int currentStep = 1;
        int currentIndex = 1;

        return canJump(river, currentIndex, currentStep);
    }

    //返回最后一步的石头位置,判断是否能跳到终点
    public static boolean canJump(int[] river, int currentIndex, int currentStep) {
        //如果最后一步能跳到终点就返回true,否则返回false
        if (currentIndex == river.length - 1) {
            return true;
        }
        //只能向前跳 原地跳并且不是终点 并且下一步不是石头 返回false
        if (currentStep == 0 && currentIndex < river.length - 1 && river[currentIndex + 1] == 0) {
            return false;
        }

        //如果最后一步不能跳到终点就返回当前位置索引 该索引必定是 1<currentIndex<=river.length-1
        if (river[currentIndex + currentStep] == 0 && river[currentIndex + currentStep + 1] == 0 && river[currentIndex + currentStep - 1] == 0) {
            return false;
        }
        //排除不能跳下一步的情况后,更新最后一步的索引和步数
        if (river[currentIndex + currentStep] == 1) {
            currentIndex = currentIndex + currentStep;
            return canJump(river, currentIndex, currentStep);
        }
        if (river[currentIndex + currentStep + 1] == 1) {
            currentIndex = currentIndex + currentStep + 1;
            currentStep++;
            return canJump(river, currentIndex, currentStep);
        }
        if (river[currentIndex + currentStep - 1] == 1) {
            currentIndex = currentIndex + currentStep - 1;
            currentStep--;
            return canJump(river, currentIndex, currentStep);
        }

        return false;
    }
}
